//
//  SkipTableQuery_17.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2020/11/24.
//

import Foundation

// 链表数据结构的跳表查询
class SkipTableQuery_17: NSObject{
    // 跳表查询
    class func query(_ head:ListNode?, value:Int) -> ListNode?{
        if head == nil || head?.next == nil {
            return nil
        }
        let listNode = SkipTableQuery_17.addIndex(head: head)// 加索引后的链表
        var tempListNode = listNode
        while tempListNode != nil{
            if tempListNode!.val < value  && (tempListNode?.next == nil || tempListNode!.next!.val > value){
                tempListNode = tempListNode?.down
            } else if(tempListNode?.val == value){
                while tempListNode?.down != nil {
                    tempListNode = tempListNode?.down
                }
                return tempListNode
            }else{
                tempListNode = tempListNode?.next
            }
        }
        
        return nil
    }
    
    // 添加索引
    class func addIndex( head: ListNode?) -> ListNode? {
        var resultHead: ListNode? = head// 存储最终的索引链的头，只会指向每一层的第一个节点

        while resultHead?.next != nil && resultHead?.next?.next != nil{
            var tempResultHead = resultHead// 活动节点
            
            let newHead: ListNode? = ListNode.init(resultHead!.val, down: resultHead)// 每一层索引都从这里创建第一个新的节点
            var tempNewHead = newHead// 新的一层的活动节点
            while tempResultHead?.next != nil && tempResultHead?.next?.next != nil {
                tempResultHead = tempResultHead?.next?.next// 每隔2个建一个索引
                tempNewHead?.next = ListNode.init(tempResultHead!.val, down: tempResultHead)// 创建索引节点
                tempNewHead = tempNewHead?.next
            }
            resultHead = newHead
        }
        return resultHead
    }
    
}
